﻿using System;

namespace SkipList
{
    public class Skiplist<Key, Value>
    {
        const int MaxNumberOfLayers = 8;

        public delegate int Comparator(Key key1, Key key2);

        public Skiplist(Comparator cmp)
        {
            rand = new Random((int)DateTime.Now.Ticks);
            this.cmp = cmp;
            head = new Node();
            head.next = new Node[MaxNumberOfLayers];
            for (int i = 0; i < MaxNumberOfLayers; ++i)
            {
                head.next[i] = Tail;
            }
        }

        public bool Insert(Key key, Value value)
        {
            int numberOfLayers = head.next.Length;
            Node[] updated = new Node[numberOfLayers];
            Node current = head;

            for (int layer = numberOfLayers - 1; layer >= 0; --layer)
            {
                while (current.next[layer] != Tail && cmp(key, current.next[layer].k) >= 0) current = current.next[layer];
                updated[layer] = current;
            }

            if (updated[0].next[0] != Tail && cmp(updated[0].k, key) == 0) return false;

            current = new Node();
            current.k = key;
            current.v = value;
            current.next = new Node[numberOfLayers];
            for (int i = numberOfLayers - 1; i >= 0; --i)
            {
                current.next[i] = updated[i].next[i];
            }

            int height = 1;
            while (height < numberOfLayers && rand.Next() % 2 == 0) ++height;

            for (int i = height - 1; i >= 0; --i)
            {
                updated[i].next[i] = current;
            }

            return true;
        }

        public bool Delete(Key key)
        {
            int numberOfLayers = head.next.Length;
            Node[] updated = new Node[numberOfLayers];
            Node current = head;

            for (int layer = numberOfLayers - 1; layer >= 0; --layer)
            {
                while (current.next[layer] != Tail && cmp(key, current.next[layer].k) > 0) current = current.next[layer];
                updated[layer] = current;
            }

            if (updated[0].next[0] == Tail || cmp(updated[0].next[0].k, key) != 0) return false;

            for (int i = numberOfLayers - 1; i >= 0; --i)
            {
                updated[i].next[i] = updated[0].next[0].next[i];
            }

            return true;
        }

        public void Dump()
        {
            for (int i = head.next.Length - 1; i >= 0; --i)
            {
                Console.Write("{0}:", i);
                Node current = head.next[i];
                while (current != Tail)
                {
                    Console.Write(" {0}.{1}", current.k, current.v);
                    current = current.next[i];
                }
                Console.WriteLine();
            }
        }

        internal class Node
        {
            public Key k;
            public Value v;

            public Node[] next;
        }

        private Node head;
        private Comparator cmp;
        private static Node Tail = new Node();
        private Random rand;
    }

    internal class Program
    {
        private static void Main(string[] args)
        {
            Skiplist<int, string> skplst = new Skiplist<int, string>((int v1, int v2) => (v1 == v2) ? 0 : (v1 > v2) ? 1 : -1);
            skplst.Insert(3, "hello");
            skplst.Insert(1, "world");
            skplst.Insert(12, "ONE");
            skplst.Insert(5, "!");
            skplst.Insert(10, "~");
            skplst.Insert(8, "C++");
            skplst.Insert(8, "C#");
            skplst.Insert(7, "Skip");
            skplst.Insert(4, "List");
            skplst.Insert(19, "ACE");
            skplst.Insert(6, "XXXX");
            skplst.Insert(9, "Parker");
            skplst.Insert(2, "Broots");
            skplst.Insert(4, "Lisa");
            skplst.Insert(11, "XVC");
            skplst.Insert(15, "Two");
            skplst.Insert(20, "You");
            skplst.Insert(14, "Fei");
            skplst.Dump();
            skplst.Delete(8);
            skplst.Delete(11);
            skplst.Delete(19);
            skplst.Dump();
        }
    }
}